package com.ma.DataStruct.lru;

import java.util.HashMap;

/**
 * 自定义双链表实现LRU
 */
public class LRUCache {
    private HashMap<Integer, Node> map;
    private DoubleList cache;
    private int cap;

    public LRUCache(int capacity) {
        this.cap = capacity;
        this.map = new HashMap<>();
        this.cache = new DoubleList();
    }

    /*
        get方法
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        makeRecently(key);
        return map.get(key).val;
    }

    /*
        put方法
     */
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            deleteKey(key);
            addRecently(key, value);
            return;
        }
        if (cap == cache.size()) {
            removeLastRecently();
        }
        addRecently(key, value);
    }

    /*
        将某个key提升为最近使用的
     */
    private void makeRecently(int key) {
        Node x = map.get(key);
        cache.remove(x);
        cache.addLast(x);
    }

    /*
        添加最近使用的元素
     */
    private void addRecently(int key, int value) {
        Node x = new Node(key, value);
        cache.addLast(x);
        map.put(key, x);
    }

    /*
        删除某一个元素
     */
    private void deleteKey(int key) {
        Node x = map.get(key);
        cache.remove(x);
        map.remove(key);
    }

    /*
        删除最久未使用的key
     */
    private void removeLastRecently() {
        Node deleteNode = cache.removeFirst();
        int deleteKey = deleteNode.key;
        map.remove(deleteKey);

    }
}
